package com.algorithm.array.sort;

import java.util.Arrays;

/**
 * topK以及快排
 * @author 韩繁文
 * @version $Id: QuickSortAlgorithm.java, v 0.1 2021-04-01 16:17 韩繁文 Exp $$
 */
public class QuickSortAlgorithm {

    //top K的问题可以采用快速排序的方法
    //给定一个数组nums,确定一个位置A，使得数组中，在A左边的数据都比A小，在A右边的都比A大

    public static int [] quickSearch(int[] nums,int left,int right,int k){
        if (left < right){
            int j = partition(nums,left,right);
            if (j == k || j == left){
                return new int []{nums[k]};
            }
            if (j>=k){
                return  quickSearch(nums,left,j,k);
            } else {
                return quickSearch(nums,j,right,k);
            }
        }
        return nums;
    }

    //快速排序，给定一个数组，对left-right下标范围内的数据进行排序，
    public static int partition(int[] nums, int low, int high) {

        int pivot = nums[low];
        while (low < high) {
            //移动high指针
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            //填坑
            if (low < high) {
                nums[low] = nums[high];
            }
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            //填坑
            if (low < high) {
                nums[high] = nums[low];
            }
        }
        //基准数放到合适的位置
        nums[low] = pivot;
        return low;
    }


    public static void main(String[] args) {
        int [] a = new int[]{5,7,13,5,7,3,1,2,4};
        int [] nums = quickSearch(a,0,a.length-1,1);
        System.out.println(Arrays.toString(nums));
    }
}
